//! @Author: DengLibin 榆霖
//! @Date:  2022-04-24 16:42:07
//! @Description: 斐波那契 数
//! 

/// @Author: DengLibin 榆霖
/// @Date:  2022-04-24 16:42:52
/// @Description: 使用递归 时间复杂度O（2^n）
fn fib(n: i32) -> i32 {
    if n < 3 {
        1
    }
    else{
        fib(n-2) + fib(n-1)
    }
}

/// @Author: DengLibin 榆霖
/// @Date:  2022-04-24 16:46:19
/// @Description: 使用循环, 动态规划
fn fib2(n: u64) -> u64 {
    if n < 3 {
        return 1;
    }

    let mut n1 = 1_u64;
    let mut n2 = 1_u64;
    let mut r = n1 + n2;
    for _ in 2..n {
        r = n1 + n2;
        n1 = n2;
        n2 = r;
    }

    return  r;
    

}


#[test]
pub fn fib_demo() {

    // println!("{}", fib(20));
    println!("{}", fib2(50));
}

